package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 分隔链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
  * 你应当 保留 两个分区中每个节点的初始相对位置。
 * @Date 2023/3/19 14:42
 */
public class Num86_PartitionList {
    public ListNode partition(ListNode head, int x) {
        /**
         * 思路：遍历原链表，将所有小于x节点的放在一个子链表l1，大于x的节点放在子链表l2，最后将l2与l1进行拼接
         * 注意：l2的尾部一定要置为null
         */
        //边界：如果头结点不存在或者只存在一个节点
        if(head ==null || head.next == null){
            return head;
        }
        //产生两个虚拟头结点，并给出节点尾部
        ListNode smallHead = new ListNode();
        ListNode bigHead = new ListNode();
        ListNode smallTial = smallHead;
        ListNode bigTail = bigHead;
        //遍历原链表，将所有小于x的节点尾插到小链表的尾部；相反的尾插到大链表的尾部
        //当head为空时结束遍历
        while (head!=null){
            if(head.val < x){
                smallTial.next = head;
                smallTial = head;
            }else{
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        //结束遍历，将大链表的尾部断开，拼接大小链表
        bigTail.next = null;
        smallTial.next = bigHead.next;
        return smallHead.next;
    }
}
